package xjggb.algorithm.排序.sort.heap;


import xjggb.algorithm.排序.sort.Sort;

/*
* 堆排序，就是选着排序的优化版
* */
public class HeapSort<T extends Comparable<T>> extends Sort<T> {
    private  int heapSize;
    @Override
    protected void sort() {
        /*
        * 原地堆
        * */
        heapSize = array.length;
        for (int i = (heapSize >> 1) - 1; i >= 0; i--) {
            siftDown(i);
        }
        /*
        * 交换堆顶元素
        * */
        while (heapSize>1){
            swap(0,--heapSize);
            /*
            * 恢复堆的性质
            * */
            siftDown(0);
        }

    }

    private void siftDown(int index) {
        T element = array[index];

        int half = heapSize >> 1;
        while (index < half) { // index必须是非叶子节点
            // 默认是左边跟父节点比
            int childIndex = (index << 1) + 1;
            T child = array[childIndex];

            int rightIndex = childIndex + 1;
            // 右子节点比左子节点大
            if (rightIndex < heapSize &&
                    cmp(array[rightIndex], child) > 0) {
                child = array[childIndex = rightIndex];
            }

            // 大于等于子节点
            if (cmp(element, child) >= 0) break;

            array[index] = child;
            index = childIndex;
        }
        array[index] = element;
    }

}
